/**
递归与链表


链表
一种常见的基础数据结构,是一种线性表，但是并不会按线性的舒徐存储数据，
而是在每一个节点里存到是下一个节点的指针(pointer)

链表与数组：线性数据结构

数组适合查找 遍历 固定长度
链表适合插入 删除 不宜过长 否则会导致遍历性能下降


 */
/*
package com.leo.第五章_面向对象下;

public class U5_L19_数据结构之链表 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		//案例：递归的调用
		//int result=digui(5);
		//System.out.println("The result is: "+result);
		
		//案例： 链表的节点调用
		pack_run();
	}
	
	//打包调用链表的方法
	public static void pack_run() {
		NodeManager nm=new NodeManager();
		nm.add(5);
		nm.add(4);
		nm.add(3);		
		nm.add(2);
		nm.add(1);
		nm.print();
		nm.del(6);
		nm.print();
		boolean res=nm.find(2);
		System.out.println("\n寻找状态: "+res);
		nm.update(1, 11);
		boolean res_up=nm.update(5, 22);
		System.out.println("\n更新状态: "+res_up);
		nm.print();
		nm.insert(0, 221);
		nm.insert(6,122);
		nm.print();
	}
	
	//递归的实例和原理
	//public static int digui(int num) {
	//	if(num==2) return 1;
	//	return num*digui(num-1);
	//}
}


//这是节点管理外部类 外部类没有构造 就一个壳 后期可以用于连接其他类或者链表
class NodeManager{
	private Node root;
	int count=1; 		//计算调用方法次数
	int currentIndex=0;	//计算外内类的索引位置
	
	//外部类添加节点 -有就指向内部类
	public void add(int data) {
		System.out.print("add调用"+count+++"->");
		if(root==null) {
			root=new Node(data);
			
		}else {
			root.addNode(data);
		}
	}
	
	//外部类删除节点 -没有就指向内部类
	public void del(int data) {
		System.out.print("del调用"+count+++"->");
		if(this.root!=null) {
			if(root.getData()==data) {
				root=root.next;
			}else {
				root.delNode(data);
			}
		}
		System.out.println("\nhead ==null");
		return ;
	}
	
	//查询是否有数据 -没有返回true or false
	public boolean find(int data) {
		System.out.print("findOuter调用"+count+++"->");
		if(this.root!=null) {
			if(this.root.getData()!=data) {
				return this.root.findinner(data);
			}else{
				return true;
			}
	    }
		return false;
	}
		
	//插入数据 -没有指向内部类
	public void insert(int index,int data) {
		System.out.print("insertOuter调用"+count+++"->");
		if(index<0)return ;
		currentIndex=0;
		if(index!=currentIndex) {
			this.root.insertinner(index, data);
		}else {
			//原来数据后移一个结点，新数据为当前节点
			Node newNode=new Node(data);
			newNode.next=this.root;
			this.root=newNode;
		}
	}
	
	//更新节点 -没有指向内部类
	public	boolean update(int olddata,int newdata) {
		System.out.print("updateOuter调用"+count+++"->");
		if(root!=null) {
			if(root.getData()!=olddata) {
				return root.updateinner(olddata, newdata);				
			}else {
				root.setData(newdata);
				return true;
			}			
		}
		return false;
	}
	
	//打印所有节点信息
	public void print() {
		System.out.println("print调用"+count+++"  ");
		if(root!=null) {
			System.out.print("\n"+root.getData());
			root.printNode();
			System.out.println();
		}else {
			System.out.println("root == null.");
		}
	}
	
	//内部类 有构造
	private class Node{
		private int data;
		private Node next;
		public Node(int data) {
			System.out.print("Node构造调用"+count+++"->");
			this.data=data;
		}
		public void setData(int data) {
			System.out.print("setData调用"+count+++"->");
			this.data=data;
		}
		
		public int getData() {
			System.out.print("getData调用"+count+++"->");
			return data;
		}
		
		//增加节点 负责递归
		public void addNode(int data) {
			System.out.print("addNode调用"+count+++"->");
			if(this.next==null) {
				this.next=new Node(data);
			}else {
				this.next.addNode(data);
			}
		}
		
		//删除节点 负责递归
		public void delNode(int data) {
			System.out.print("delNode调用"+count+++"->");
			if(this.next!=null) {
				if(this.next.getData()==data) {
					this.next=this.next.next;
				}else {
					this.next.delNode(data);					
				}
			}
			//下个节点为空，当前节点不匹配 return false
			if(this.next==null && this.getData()!=data) {
				System.out.println("\n此data不在此链表内.");
				return;
		}
		}
		
		//跟新节点
		public  boolean updateinner(int olddata,int newdata) {
			System.out.print("updateinner调用"+count+++"->");
			if(this.next!=null) {
				//下个节点不匹配递归 匹配更新新数据
				if(this.next.getData()!=olddata) {
					this.next.updateinner(olddata, newdata);
				}else {
					this.next.setData(newdata);
				}
			}
			return false;
		}
		
		//查询方法的内部类 负责递归
		public boolean findinner(int data) {
			System.out.print("findinner调用"+count+++"->");
			if(this.next!=null) {
				if(this.next.getData()!=data) {
					return this.next.findinner(data);
				}else {
					return true;
				}
			}else {
				return false;
			}
		}
		
		//插入方法的内部类 负责递归
		public void insertinner(int index,int data) {
			System.out.print("insertinner调用"+count+++"->");
			currentIndex++;
			if(index!=currentIndex) {
				this.next.insertinner(index, data);
			}else {
				Node newNode=new Node(data);
				newNode.next=this.next;
				this.next=newNode;
			}			
		}
		
		//打印方法的内部类 负责递归
		public void printNode() {		
			if(this.next!=null) {
				System.out.print("->"+this.next.data);
				this.next.printNode();
			}else {
				System.out.println("\nNode next == 待续...");
			}
			System.out.print("printNode调用"+count+++"->");	
		}
	}
}
*/